package tr.edu.yildiz.markov.viterbi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import tr.edu.yildiz.markov.education.Educator;
import tr.edu.yildiz.util.CharUtils;

/**
 * Applies Viterbi Algorithm with matrixes which are calculated in
 * {@link Educator} class.
 * 
 * @author Onur Ulusu
 * 
 */
public class ViterbiCalculator {

	/**
	 * @param observedWord
	 *            observed faulty word to be corrected.
	 * @param initialStateProbs
	 *            Initial state probabilities
	 * @param stateTransitionProbMatrix
	 *            State transition probability matrix
	 * 
	 * @param outputProbabilityMatrix
	 *            Output probability matrix
	 * @return corrected word using viterbi
	 */
	public String viterbi(String observedWord, double[] initialStateProbs,
			double[][] stateTransitionProbMatrix,
			double[][] outputProbabilityMatrix) {

		double[][] V = new double[observedWord.length()][26];

		// Run viterbi for t = 0
		for (int y = 0; y < 26; y++) {
			V[0][y] = initialStateProbs[y]
					* outputProbabilityMatrix[y][CharUtils
							.getNumericSeqOfChar(observedWord.charAt(0))];
		}
		List<Double> list = new ArrayList<Double>();
		// Run viterbi for t > 0
		for (int t = 1; t < observedWord.length(); t++) {

			for (int y = 0; y < 26; y++) {
				for (int z = 0; z < 26; z++) {
					list.add(V[t - 1][z] * stateTransitionProbMatrix[z][y]);
				}
				// Finding max probability which are calculated from previous
				// state and transition matrix.
				Double max = Collections.max(list);
				V[t][y] = max
						* outputProbabilityMatrix[y][CharUtils
								.getNumericSeqOfChar(observedWord.charAt(t))];
				list.clear();
			}
		}

		// Determining most probable path from max probabilited values...
		double largest = 0;
		int largestIndex = 0;
		String hiddenWord = "";

		for (int t = 0; t < observedWord.length(); t++) {
			for (int i = 0; i < V[0].length; i++) {
				if (V[t][i] > largest) {
					largest = V[t][i];
					largestIndex = i;
				}
			}
			hiddenWord += CharUtils.getCharofGivenSeq(largestIndex);
			largest = 0;
			largestIndex = 0;
		}

		return hiddenWord;
	}
}
